Processing math: 100%

$\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor} \newcommand{\ceil}[1]{\left\lceil{#1}\right\rceil} \renewcommand{\mod}{\,\mathrm{mod}\,} \renewcommand{\div}{\,\mathrm{div}\,} \newcommand{\metar}{\,\mathrm{m}} \newcommand{\cm}{\,\mathrm{cm}} \newcommand{\dm}{\,\mathrm{dm}} \newcommand{\litar}{\,\mathrm{l}} \newcommand{\km}{\,\mathrm{km}} \newcommand{\s}{\,\mathrm{s}} \newcommand{\h}{\,\mathrm{h}} \newcommand{\minut}{\,\mathrm{min}} \newcommand{\kmh}{\,\mathrm{\frac{km}{h}}} \newcommand{\ms}{\,\mathrm{\frac{m}{s}}} \newcommand{\mss}{\,\mathrm{\frac{m}{s^2}}} \newcommand{\mmin}{\,\mathrm{\frac{m}{min}}} \newcommand{\smin}{\,\mathrm{\frac{s}{min}}}$

Prijavi problem

Obeleži sve kategorije koje odgovaraju problemu

Problem sa prikazivanjem Stranica ili neki deo stranice se ne prikazuje očekivano.

Problemi sa zadatkom Neispravni primeri, neočekivana rešenja, postavka...

Problemi sa grader-om Dugo čekam na rezultat, ne dobijam rezultat...

Problemi sa sadržajem Greška u tekstu, neispravna formula...

Ostalo Ne mogu da se logujem, problem sa kontrolnom tablom...

Još detalja - opišite nam problem

Методичка збирка задатака из алгоритмике - елементарне технике анализе и конструкције алгоритама

Анализа коректности алгоритама
- Аритметички троугао
- Тробојка
- Двобојка
- Први који није дељив
- Најмањи број који није збир елемената скупа
- Бинарни запис
- Растављање на просте чиниоце
Сложеност израчунавања
- Замена итерације формулом
  - Спортске припреме
  - N-ти дан тренинга
  - Аритметички троугао
  - Аритметички квадрат
  - Број подстрингова који почињу и завршавају са 1
  - Двојке и тројке дељиве са 3
  - Недостајући број
  - Број дељивих у интервалу
  - Хлебови
  - Дељиви око броја
  - Максимални принос
  - Растављања на збир узастопних
  - Питагорине тројке
  - Највећи заједнички делилац
- Одсецање
  - Прост број
  - Ератостеново сито
  - Збир простих прост
  - Серија сјајних партија
  - Најдужа серија победа
  - Број растућих сегмената
  - Максимални збир сегмента
- Сортирање
  - Функције сортирања
    - Сортирање бројева
    - Медијана
    - Цик цак селекција
  - Сортирање по разним критеријумима
    - Сортирање такмичара
    - Највреднији предмети
    - Сортирање линија
    - Сортирање по просеку
    - Ранг сваког елемента
  - Сортирање разврставањем
    - Сортирање пребројавањем
    - Разврставање по општинама
    - Разврставање по првом слову
    - Сортирање бројева вишеструким разврставањем (RadixSort)
  - Обрада дупликата (поновљених вредности у низу)
    - Дупликати
    - Највећи поновљени елемент
    - Двоструки студент
    - Неупарени елемент
    - Број различитих дужина дужи
    - Најбројнији елемент
  - Груписање блиских вредности
    - Праведна подела чоколадица
    - Најближе собе
    - Најбројнији подскуп који садржи узастопне целе бројеве
  - Свођење на канонски облик
    - Анаграм
    - Провера пермутација
    - D-пермутација
    - Анаграми
  - Сортирање интервала
    - Најбројнији пресек интервала
    - Покривање праве затвореним интервалима
  - Остале примене сортирања
    - Коректни телефони
    - Хиршов h-индекс
    - Збир минимума тројки
- Бинарна претрага
  - Бинарна претрага елемента у низу
    - Провера бар-кодова
    - Број парова датог збира
    - XOR
    - Квадрати
    - Ранг сваког елемента
    - i-ти на месту i
    - Штерн-Брокоово стабло
  - Бинарна претрага преломне тачке
    - Први већи и последњи мањи
    - Провера бар-кодова
    - Број такмичара изнад прага
    - Тастатура и миш
    - Кружне зоне
    - Разлика висина
    - Најближи датом елементу
    - Оптимални сервис
    - Први који није дељив
    - Збирови свих малих вредности
    - К-најближих датом
    - Врх планине
    - i-ти на месту i
    - Минимум ротираног сортираног низа
    - Претрага ротираног сортираног низа
  - Проналажење оптималне вредности решења бинарном претрагом
    - Дрва
    - Арматура
    - Конференција
    - Најкраћа подниска која садржи све дате карактере
    - Хиршов h-индекс
    - Највећи квадрат у хистограму
    - Муцајући подниз
    - Пуно фигурица
    - Кувар
    - Градња
    - К-то растојање
    - К-ти по реду број дељив или са a или са b
    - Гласници
- Скупови и мапе (речници)
  - Дупликати
  - Неупарени елемент
  - Двоструки студент
  - Најбројнији елемент
  - Рачуни
  - Сортирање бројева
  - Квадрати
  - Највећи поновљени елемент
  - Број различитих дужина дужи
  - Број парова датог збира
  - Тројке датог збира (3sum)
  - Анаграм
  - Провера пермутација
  - D-пермутација
  - Анаграми
  - Мађионичар довољне снаге
  - Најјачи мађионичар
- Инкременталност
  - Инкременталност збира и производа
    - Највећи збир префикса
    - Факторијели од 1 до n
    - Хармонијски пи
    - Сума реда
    - Оптимални сервис
  - Инкременталност минимума и максимума
    - Најбољи "сабмит"
    - Поглед на реку
    - Ред особа
    - Најдужи сегмент који садржи узастопне бројеве
    - Добри такмичари
  - Инкременталност - остале статистике
    - Рутер
    - Централа
    - Највећи тежински збир после цикличног померања
    - Дрва
    - Хиршов h-индекс
    - Максимални збир сегмента фиксираног почетка
  - Инкременталност - вишедимензионални низови
    - Суме трапеза
    - Минимуми правоугаоника
  - Покретни прозор фиксне ширине
    - Пермутоване подниске
    - Сегмент дужине k највећег просека
    - Панграми
  - Инкременталност - суфикси до сваке позиције у низу
    - Број растућих сегмената
    - Најдужа серија победа
    - Серија сјајних партија
    - Број сегмената исте парности
    - Број сегмената са различитим елементима
    - Максимални збир сегмента
- Збирови префикса и разлике суседних елемената низа
  - Аритметички троугао
  - Збирови сегмената
  - Максимални збир сегмента
  - Паметна куповина акција
  - Сегмент датог збира у низу целих бројева
  - Сегмент датог збира у низу природних бројева
  - Кајмак
  - Број сегмената чији је збир дељив са k
  - Слаткиши за сав новац
  - Кружни пут
  - Збирови правоугаоника
  - Пар производа у ранцу
  - Попуњавање празнина
  - Збир подниза карата
  - Највећи НЗД низа након замене једног елемента
  - Увећавање сегмената
  - Најбројнији пресек интервала
  - Пермутација са највећим збиром упита
- Техника два показивача
  - Обједињавање
  - Сортирани квадрати бројева
  - Заједнички елементи три уређена низа
  - Близанци
  - Прости чиниоци 235
  - Сегмент датог збира у низу природних бројева
  - Број сегмената малог збира
  - Кајмак
  - Тастатура и миш
  - Двобојка
  - Тробојка
  - Оптимални сервис
  - Два блиска предајника
  - Светиљка
  - Број парова датог збира
  - Тројке датог збира (3sum)
  - Разлика висина
  - Пуно фигурица
  - Пар производа у ранцу
  - Број сегмената са различитим елементима
  - Конференција
  - Најкраћа подниска која садржи све дате карактере
  - Квадратно-троугаони бројеви
  - Кружни пут
  - Двоструко сортирана претрага
Конструкција алгоритама рекурзијом тј. индукцијом
- Елементарне петље изражене рекурзивно
  - Бројеви од a до b
  - Бројање у игри жмурке
  - Троцифрени парни бројеви
  - Одбројавање уназад
  - Подела интервала на једнаке делове
  - Геометријска серија
  - Збир n бројева
  - Читање до нуле
  - Просек свих бројева до краја улаза
  - Прерачунавање миља у километре
  - Табелирање функције
  - Факторијел
  - Степен
  - Једнакост растојања
  - Средине
  - Најнижа температура
  - Други на ранг листи
  - Разлика сума до маx и од маx
  - Негативан број
  - Прва негативна температура
  - Последња негативна температура
  - Бројеви дељиви са 3
  - Просек одличних
  - Број и збир цифара броја
  - Провера бар-кодова
  - Обједињавање
  - Број парова датог збира
  - Последњих k цифара степена
- Репна рекурзија
  - Збир n бројева
  - Број и збир цифара броја
  - Факторијел
  - Степен
  - Једнакост растојања
  - Најнижа температура
  - Други на ранг листи
  - Прва негативна температура
  - Последња негативна температура
  - Просек одличних
- Извођење итеративних алгоритама из рекурзивних
  - Грејов код
  - Морзеов низ
  - Избацивање цифара на све начине
  - Не садрже цифру 3
  - Збир највећих непрарних делилаца
  - Дужина сажете форме ниске
  - Слово у сажетој форми ниске
  - Ханојске куле
  - Функција пар-непар
  - Дијаметар бинарног дрвета
  - Фактори неравнотеже бинарног дрвета
  - Звезда
  - Апсолутни победник на гласању
  - Цикличко померање за k места улево
- Претрага у дубину
  - Број белих области
  - Највећа заражена област
  - Minesweeper отварање
- Рекурзивни спуст
  - Превођење потпуно заграђеног израза у постфиксни облик
  - Вредност потпуно заграђеног израза
  - Вредност израза у коме нема заграда
  - Вредност израза
Генерисање комбинаторних објеката
- Следећа варијација
- Следећи подскуп
- Следећи бинарни низ без суседних јединица
- Следећа комбинација
- Следећа пермутација
- Следећа партиција
- Лексикографски наредна шетња
- Све варијације
- Све речи од датих слова
- Сви подскупови
- Сви подскупови лексикографски
- Сви бинарни низови без суседних јединица
- Бројеви који у бинарном запису немају две суседне нуле
- Све комбинације
- Све комбинације са понављањем
- Све пермутације
- Сви палиндроми од дате речи
- Све партиције
- Све једноцифрене партиције
- Сви распореди заграда
- Варијације без понављања
- Покривање табле 2xk доминама 2x1
- Разлика суседних цифара k
- Комплетан Грејов код
- Подела на палиндромске подниске
- K-та тешка реч
- Број израза дате вредности
- Сви распореди заграда дате дубине
- Све допуне заграда
- Допуна бинарних низова без суседних јединица
- Вагони са 4 седишта
Стек и ред -- основе
- Стек
  - Линије у обратном редоследу
  - Историја веб-прегледача
  - Сажимање путања
  - Упареност заграда
  - Push-pop реконструкција
  - Брисање парова узастопних једнаких карактера
  - Сажимање серија узастопних једнаких елемената
  - Сажимање бекства из лавиринта
  - Све путање у пуном стаблу на основу префиксног обиласка
  - Линијски едитор
  - Сортирање бројева
  - Ханојске куле
- Ред
  - Сегмент дужине k највећег просека
  - Последњих k линија
  - Сортирање - сви испред мањи или сви испред већи
  - Јосифов проблем
  - Кружна листа
  - Прости чиниоци 235
  - Најдужи сегмент који садржи узастопне бројеве
  - Ограничена историја прегледача
  - Максимална бијекција
Претрага у дубину и ширину
- Претрага у дубину
  - Број белих области
  - Највећа заражена област
  - Minesweeper отварање
  - Flood fill
  - Пут кроз лавиринт
  - Обојени лавиринт
  - Максимални безбедни пут
  - Дужина најдужег проходног пута
- Претрага у ширину
  - Број белих области
  - Пут кроз лавиринт
  - Најкраћи пут кроз лавиринт
  - Број потеза коња
  - Најдаље копно
  - Уклањање погрешних заграда
Бектрекинг и груба сила
- Распоређивање n дама на шаховској табли
- Судоку
- Латински квадрати
- Скакачева тура
- Бојење графа са три боје
- К бојење
- Број поднизова датог збира
- Мерење са n тегова
- Мерење са n врста тегова
- Братска подела
- Сви n-тоцифрени бројеви са датим збиром цифара
- Збир суседних пун квадрат
Подели па владај
- Тримини
- Сортирање бројева
- Медијана
- Збир k најбољих
- Силуета града
- Број сегмената у низу целих бројева чији је збир најмање K
- Број инверзија
- Број елемената десно од датог елемента већих или једнаких од њега
- Број сортираних тројки
- Бинарне слике
- Максимални збир сегмента
- Паметна куповина акција
- Најближи пар тачака
- Трећи обилазак
Динамичко програмирање
- Бројање комбинаторних објеката
  - Број комбинација
  - Број комбинација са понављањем
  - Број партиција
  - Број цик-цак партиција
  - Број начина разлагања на збир различитих n-тих степена
  - Дигитални бројач
  - Низови 0 и 1 без две суседне 1 - редни број
  - Број начина декодирања
  - Примитивни бинарни записи
  - Број појављивања подниске
  - Поплочавање табле 3×k плочицама 2×1
- Оптимизација коришћењем динамичког програмирања
  - Максимални збир на путу кроз матрицу
  - Максимални пут кроз матрицу
  - Сви збирови обиласка матрице
  - Цилиндрична матрица
  - Падајуће лоптице
  - Најдужи пут низбрдо
  - Едит растојање
  - Најдужи заједнички подниз две ниске
  - Најдужа заједничка подниска
  - Најдужи подниз који се понавља
  - Најдужа подниска који се понавља без преклапања
  - Минимуми правоугаоника
  - Суме трапеза
  - Максимални збир сегмента
  - Максимални збир несуседних елемената низа
  - Исплата са најмање новчића
  - Разлагање на збир квадрата
  - Најдужи растући подниз
  - Допуна нулама до највећег скаларног производа
  - Удруживање поруџбина
  - Најдужи подниз палиндром
  - Оптимално множење матрица
  - Подскуп максималног збира дељивог са k
  - Превоз предмета лифтом
- Пчеле и трутови
Грамзиви алгоритми
- Реч у реч прецртавањем слова
- Жаба на камењу
- Неопадајућа растојања суседних елемената
- Шаховске екипе
- Ментори
- Распоред са најмањим бројем учионица
- Распоред активности
- Зли учитељ
- Мали поштар
- Минимална сума два броја формирана од датих цифара
- Најмањи број надовезивањем више бројева
- Излог са два реда књига
- Гласници
- Мост
- Спасавање чамцем
- Квалитетни радници
- Кодирање текста са што мање битова
- Распоред са најмањим закашњењем
- Разломљени ранац
- Селидба
- Исплата са посебним новчићима
Напреднија употреба структура података
- Ред са приоритетом
  - Сортирање бројева
  - Збир k најбољих
  - Збирови квадрата
  - Степени природних бројева
  - K-ти највећи збир пара елемената два низа
  - Ажурирање медијане
  - Сумњиве трансакције
  - Силуета града
  - Својство 132
  - Лоши такмичари у односу на свој рејтинг
  - Бонус најлошијем играчу
  - Индуктивни скуп
- Апстрактни типови података
  - Хип
  - Мапа
  - Скуп
  - Вектор
  - Мапа са увећањем
  - Фреквенцијски стек
  - Стек и максимуми
  - Ред без дупликата
- Синтакстичка анализа
  - Вредност постфиксног израза
  - Превођење потпуно заграђеног израза у постфиксни облик
  - Вредност израза
- Монотони стек и ред
  - Најближи већи претходник
  - Најближи већи следбеник
  - Највећи правоугаоник у хистограму
  - Највећи квадрат у хистограму
  - Збир минимума
  - Сегменти оивичени максимумима
  - Својство 132
  - Маx сегмената дужине k

Не садрже цифру 3

време	меморија	улаз	излаз
0,1 s	64 Mb	стандардни излаз	стандардни улаз

Напиши програм који одређује колико природних бројева из интервала $[0, n]$ не садрже цифру 3 у свом декадном запису.

Улаз

Прва линија стандардног улаза садржи природан број $n$ ( $n \leq 2 \cdot 10^9$ ).

Излаз

У првој линији стандардног излаза приказати тражени резултат.

Пример 1

Улаз

Излаз

Објашњење

У интервалу $[0, 15]$ постоји 16 бројева, а бројеви $3$ и $13$ једини садрже цифру $3$ .

Пример 2

Улаз

Излаз

Пример 3

Улаз

Излаз

Морате бити улоговани како бисте послали задатак на евалуацију.